/*
 * @lc app=leetcode.cn id=432 lang=golang
 * @lcpr version=30118
 *
 * [432] 全 O(1) 的数据结构
 */

// @lcpr-template-start
package main

// @lcpr-template-end
// @lc code=start
type Node struct {
	Keys  map[string]bool // 当作set用
	Count int
	Next  *Node
	Prev  *Node
}

type AllOne struct {
	Head *Node
	M    map[string]*Node
}

func Constructor() AllOne {
	Head := &Node{Keys: make(map[string]bool), Count: 0}
	Head.Next = Head
	Head.Prev = Head
	return AllOne{Head: Head, M: make(map[string]*Node)}
}

func (this *AllOne) Inc(key string) {
	if node, ok := this.M[key]; ok {
		delete(node.Keys, key)

		if node.Next.Count == node.Count+1 {
			this.M[key] = node.Next
			node.Next.Keys[key] = true
		} else {
			keyNode := &Node{Keys: map[string]bool{key: true},
				Count: node.Count + 1}
			this.InsertAfter(node, keyNode)
			this.M[key] = keyNode
		}

		if len(node.Keys) == 0 {
			this.Remove(node)
		}

	} else {
		if this.Head.Next.Count != 1 {
			this.InsertAfter(this.Head, &Node{Keys: map[string]bool{key: true},
				Count: 1})
		} else {
			this.Head.Next.Keys[key] = true
		}
		this.M[key] = this.Head.Next
	}
}

func (this *AllOne) Dec(key string) {
	if node, ok := this.M[key]; ok {
		delete(node.Keys, key)
		if node.Count == 1 {
			delete(this.M, key)
		} else {
			if node.Prev.Count == node.Count-1 {
				node.Prev.Keys[key] = true
				this.M[key] = node.Prev
			} else {
				newNode := &Node{Keys: map[string]bool{key: true},
					Count: node.Count - 1}
				this.InsertAfter(node.Prev, newNode)
				this.M[key] = newNode
			}
		}
		if len(node.Keys) == 0 {
			this.Remove(node)
		}
	}
	return
}

func (this *AllOne) GetMaxKey() string {
	keys := this.Head.Prev.Keys
	if len(keys) == 0 {
		return ""
	} else {
		for k := range keys {
			return k
		}
	}
	return ""
}

func (this *AllOne) GetMinKey() string {
	if len(this.Head.Next.Keys) != 0 {
		for k := range this.Head.Next.Keys {
			return k
		}
	} else {

	}
	return ""
}

func (this *AllOne) InsertAfter(node, newNode *Node) {
	newNode.Next = node.Next
	newNode.Prev = node

	node.Next.Prev = newNode
	node.Next = newNode
}

func (this *AllOne) Remove(node *Node) {
	prev := node.Prev
	next := node.Next
	prev.Next = next
	next.Prev = prev
}

/**
 * Your AllOne object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Inc(key);
 * obj.Dec(key);
 * param_3 := obj.GetMaxKey();
 * param_4 := obj.GetMinKey();
 */
// @lc code=end
